/*
题目: 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
https://leetcode.cn/problems/longest-palindromic-substring/
 */
public class LongestPalindrome {
    public String longestPalindrome(String s) {
        // 双指针法 and 动态规划
        int n = s.length();
        if (n <= 1) return s;
        // 表示 row -> col 字符串是不是回文串
        boolean[][] dp = new boolean[n][n];

        int maxLength = 1;// 记录最长回文串长度
        int begin = 0; //记录最长回文串的开始下标
        initDp(dp, n);
        for (int i = 1; i < n; i ++) { // 以 i 结尾的字符串
            for (int j = 0; j < i; j ++) { // 以 j 开头
                if (s.charAt(i) == s.charAt(j)) {
                    if (i - j <= 2) { //去两边后, 如果没剩, 或者只剩一个元素, 那就是回文串
                        dp[j][i] = true;
                    } else {
                        dp[j][i] = dp[j + 1][i - 1];
                    }
                    // 更新 maxLength 值
                    if (dp[j][i] && i - j + 1 > maxLength) {
                        begin = j;
                        maxLength = i - j + 1;
                    }
                }
            }
        }

        return s.substring(begin, begin + maxLength);
    }

    // 初始化, 所有长度为 1 的都是回文串
    private void initDp(boolean[][] dp, int n) {
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
    }
}
